package 中等.位运算;

/**
 * 给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。
 * 注意，除非字符串就是 "0"，否则返回的字符串中不能含有前导零。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/convert-to-base-2
 */
public class 负二进制转换_1017 {

    public static void main(String[] args) {

        System.out.println(baseNeg2(3));

    }

    /**
     * 类似十进制转二进制，注意二进制位必须是 1 或者 0，
     * 如果当前数为偶数那么是 0，奇数是 1，
     * 偶数：
     * nextN * -2 + 0 == n
     * 奇数：
     * nextN * -2 + 1 == n
     * 计算 2 转负二进制
     * -2    n    bit
     * -2    2    0
     * -2   -1    1
     * -2    1    1
     * -     0
     */
    public static String baseNeg2(int n) {
        if (n == 0) return "0";
        StringBuilder builder = new StringBuilder();

        while (n != 0) {
            if (n % 2 == 0) {
                n = n / -2;
                builder.append("0");
            } else {
                n = (n - 1) / -2;
                builder.append("1");
            }
        }

        StringBuilder reverse = builder.reverse();
        int l = 0;
        while (l < reverse.length() && reverse.charAt(l) == '0') l++;
        return reverse.substring(l);
    }

}
